import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Leetcode855 {

    //    public static void main(String[] args) {
//        ExamRoom examRoom = new ExamRoom(10);
//        System.out.println(examRoom.seat());
//        System.out.println(examRoom.seat());
//        System.out.println(examRoom.seat());
//        System.out.println(examRoom.seat());
//        examRoom.leave(4);
//        System.out.println(examRoom.seat());
//    }
    public static void main(String[] args) {
        ExamRoom examRoom = new ExamRoom(8);
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        examRoom.leave(0);
        examRoom.leave(7);
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
        System.out.println(examRoom.seat());
    }

    static class ExamRoom {
        int n;

        List<Integer> flag;

        public ExamRoom(int n) {
            this.n = n - 1;
            this.flag = new ArrayList<>();
        }

        public int seat() {
            if (flag.size() == 0) {
                flag.add(0);
                return 0;
            }

            if (flag.size() == 1) {
                if (flag.get(0) > n - flag.get(0)) {
                    flag.add(0, 0);
                    return 0;
                }

                flag.add(n);
                return n;
            }

            int maxDiff = 0;
            int maxDiffIndex = 0;
            for (int i = 1; i < flag.size(); i++) {
                int diff = (flag.get(i) - flag.get(i - 1)) / 2;
                if (diff > maxDiff) {
                    maxDiffIndex = i - 1;
                    maxDiff = diff;
                }
            }

            if (flag.get(0) > maxDiff / 2) {
                flag.add(0, 0);
                return 0;
            }

            if (n - flag.get(flag.size() - 1) > maxDiff) {
                flag.add(flag.size(), n);
                return n;
            }

            int res = flag.get(maxDiffIndex) + maxDiff;
            flag.add(maxDiffIndex + 1, res);

            return res;
        }

        public void leave(int p) {
            flag.remove(Integer.valueOf(p));
        }
    }
}

